题解 P3959 【宝藏】

发表于 | 更新于

题意$:$给定一张 $n$个点$,m$条边的有重边的图，找到一个生成树，使得每条边的权值$ \times$到根的距离最小

在任意时刻，我们关心的只有我们已经把多少点加进树了，以及树的最大树高是多少。

设$f[S][i]$为当前树已经包含集合$S$中的点，并且树高是$i$。

那么怎么判断$S_{0}$在转移中是否合法呢？我们设$G_{S}$是$S$能拓展到的边的集合，显然$G$数组是可以预处理出来的。

$f[S][i]=min(f[S_0][i-1]+pay)$，其中满足$S_{0}$是$S$的子集，通过$S_{0}$加边一定可以联结成$S$。$pay$是这次加边的花费。

设$ss=S~xor~S_{0}$，即$ss$是在$S$但不在$S_{0}$中的元素。

这里$pay$的计算显然是对于每个$ss$中的元素找$S_{0}$中的元素与它最短一条的边求和后$\times $树高(即$i$)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int cnt,ma[393939],head[393939],f[15][40000],dis[39][39],ans;
signed main(){
    int n=read(),m=read();memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=m;++i){
        int u=read(),v=read(),d=read();
        dis[v][u]=dis[u][v]=min(dis[v][u],d);
    }
    memset(f,0x3f,sizeof(f));
    for (re int i=1;i<=n;++i)dis[i][i]=0,f[0][1<<(i-1)]=0;
    for (re int i=1;i<=(1<<n)-1;++i)
        for (re int j=1;j<=n;++j)
            if (i&(1<<(j-1)))
                for (re int k=1;k<=n;++k)
                    if (dis[j][k]!=inf)
                        ma[i]|=1<<(k-1);
    for (int s=2;s<=(1<<n)-1;++s)
        for (re int i=s-1;i;i=s&(i-1))
            if ((s|ma[i])==ma[i]){
                int res=0,st=s^i;
                for (re int k=1;k<=n;++k)
                    if (st&(1<<(k-1))){
                        int t=inf;
                        for (re int p=1;p<=n;++p)
                            if (i&(1<<(p-1)))
                                t=min(t,dis[p][k]);
                        res+=t;
                        if (res>inf)break;
                    }
                if (res<inf)
                    for (re int t=1;t<n;++t)
                        f[t][s]=min(f[t][s],f[t-1][i]+res*t);
            }
    ans=inf;
    for (int i=0;i<n;++i)
        ans=min(ans,f[i][(1<<n)-1]);
    printf("%d",ans);
    return 0;
}